#include <iostream>
#include <vector>

using namespace std;


class Solution
{
public:
    bool updateMid(int p1, int p2, int midInd, int n, int& mid)
    {
        if(p1 + p2 == midInd)
        {
            mid = n;
            return true;
        }
        return false;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        // find mid indexes
        int len1 = nums1.size(), len2 = nums2.size();
        int sumLen = len1 + len2;
        int midInd1 = 0, midInd2 = 0;
        if(sumLen % 2)
        {
            midInd1 = midInd2 = (sumLen - 1) / 2;
        }
        else
        {
            midInd1 = (sumLen - 2) >> 1;
            midInd2 = sumLen >> 1;
        }


        // find mid value, 3 situations
        int mid1 = 0, mid2 = 0;
        // Situation 1, len2 == 0
        if(len2 == 0)
        {
            mid1 = nums1[midInd1];
            mid2 = nums1[midInd2];
            return double((mid1 + mid2) / 2.);
        }
        // Situation 2, len1 == 0
        if(len1 == 0)
        {
            mid1 = nums2[midInd1];
            mid2 = nums2[midInd2];
            return double((mid1 + mid2) / 2.);
        }
        // Situation 3, len1>0 && len2>0
        int p1 = 0, p2 = 0;
        bool flag1 = false, flag2 = false;
        while(p1 < len1 || p2 < len2)
        {
            if(flag1 && flag2)
            {
                break;
            }

            if(p1 == len1)
            {
                flag1 = flag1 ? flag1 : updateMid(p1, p2, midInd1, nums2[p2], mid1);
                flag2 = flag2 ? flag2 : updateMid(p1, p2, midInd2, nums2[p2], mid2);
                p2++;
                continue;
            }

            if(p2 == len2)
            {
                flag1 = flag1 ? flag1 : updateMid(p1, p2, midInd1, nums1[p1], mid1);
                flag2 = flag2 ? flag2 : updateMid(p1, p2, midInd2, nums1[p1], mid2);
                p1++;
                continue;
            }

            if(nums1[p1] < nums2[p2])
            {
                flag1 = flag1 ? flag1 : updateMid(p1, p2, midInd1, nums1[p1], mid1);
                flag2 = flag2 ? flag2 : updateMid(p1, p2, midInd2, nums1[p1], mid2);
                p1++;
            }
            else
            {
                flag1 = flag1 ? flag1 : updateMid(p1, p2, midInd1, nums2[p2], mid1);
                flag2 = flag2 ? flag2 : updateMid(p1, p2, midInd2, nums2[p2], mid2);
                p2++;
            }
        }
        return double((mid1 + mid2) / 2.);
    }
};
